package com.lw.leetcode.hash.b;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * 851. 喧闹和富有
 *
 * @author liw
 * @version 1.0
 * @date 2021/12/15 13:17
 */
public class LoudAndRich {


    public static void main(String[] args) {


        Map<Integer, List<Integer>> map = new HashMap<>();

        List<Integer> list = map.get(1);
        if (list == null) {
            list = new ArrayList<>();
            map.put(1, list);
        }
        list.add(2);

        map.computeIfAbsent(1, v -> new ArrayList<>()).add(1);


        Map<Integer, Integer> map1 = new HashMap<>();

        Integer integer = map1.get(1);
        if (integer == null) {
            map1.put(1, 1);
        } else {
            map1.put(1, integer + 1);
        }

        map1.merge(1, 1, (a, b) -> a + b);


        LoudAndRich test = new LoudAndRich();

        // {5,5,2,5,4,5,6,7}
        int[][] arr = {{1, 0}, {2, 1}, {3, 1}, {3, 7}, {4, 3}, {5, 3}, {6, 3}};
        int[] ints = {3, 2, 5, 4, 6, 1, 7, 0};

        // {0}
//        int[][] arr = {};
//        int[] ints = {0};

        // [0,1]
//        int[][] arr = {};
//        int[] ints = {1, 0};

        int[] ints1 = test.loudAndRich(arr, ints);
        System.out.println(Arrays.toString(ints1));
    }

    private Map<Integer, Node> map;
    private Map<Integer, Node> cache = new HashMap<>();

    public int[] loudAndRich(int[][] richer, int[] quiet) {
        Map<Integer, Node> map = new HashMap<>();
        int length = quiet.length;
        for (int[] ints : richer) {
            int n0 = ints[0];
            int n1 = ints[1];
            Node a = map.computeIfAbsent(n1, v -> new Node(n1, quiet[n1]));
            Node b = map.computeIfAbsent(n0, v -> new Node(n0, quiet[n0]));
            a.next.add(b);
        }
        int[] arr = new int[length];
        this.map = map;
        for (int i = 0; i < length; i++) {
            Node node = find(i);
            arr[i] = node.v;
        }
        return arr;
    }

    private Node find(int key) {
        if (cache.containsKey(key)) {
            return cache.get(key);
        }
        Node node = map.get(key);
        if (node == null) {
            return new Node(key, key);
        }
        List<Node> next = node.next;
        if (next.isEmpty()) {
            return node;
        }
        Node item = node;
        for (Node no : next) {
            Node n = find(no.v);
            item = item.q > n.q ? n : item;
        }
        cache.put(key, item);
        return item;
    }

    class Node {
        public Node(int v, int q) {
            this.v = v;
            this.q = q;
        }

        private int v;
        private int q;
        private List<Node> next = new ArrayList<>();
    }

}
